Section: Scientific Foundations

Gröbner basis and triangular sets

Participants : J.C. Faugère, G. Renault, M. Safey El Din, P.J. Spaenlehauer, D. Wang, C. Mou, J. Svartz.

Let us denote by $K[X_1,...,X_n]$ the ring of polynomials with coefficients in a field $K$ and indeterminates $X_1,...,X_n$ and $S=\{P_1,...,P_s\}$ any subset of $K[X_1,...,X_n]$. A point $x\in {ℂ}^n$ is a zero of $S$ if $P_i\left(x\right)=0i\in [1...s]$.

The ideal $ℐ=\langle P_1,...,P_s\rangle$ generated by $P_1,...,P_s$ is the set of polynomials in $K[X_1,...,X_n]$ constituted by all the combinations ${\displaystyle \sum _{k=1}^R{P}_k{U}_k}$ with $U_k\in \mathbb{Q}[X_1,...,X_n]$. Since every element of $ℐ$ vanishes at each zero of $S$, we denote by $V_C\left(S\right)=V_C\left(I\right)=\{x\in C^n|p\left(x\right)=0\forall p\in ℐ\}$ (resp. $V_R\left(S\right)=V_R\left(I\right)=V_{ℂ}\left(I\right)\bigcap {ℝ}^n$), the set of complex (resp. real) zeros of $S$, where $R$ is a real closed field containing $K$ and $C$ its algebraic closure.

One Gröbner basis' main property is to provide an algorithmic method for deciding if a polynomial belongs or not to an ideal through a reduction function denoted "$\text{Reduce}$" from now.

If $G$ is a Gröbner basis of an ideal $ℐ\subset \mathbb{Q}[X_1,...,X_n]$ for any monomial ordering $<$.

• (i)

  a polynomial $p\in \mathbb{Q}[X_1,...,X_n]$ belongs to $ℐ$ if and only if $\text{Reduce}(p,G,<)=0$,

• (ii)

  Reduce($p$,$G$,$<$) does not depend on the order of the polynomials in the list $G$, thus, this is a canonical reduced expression modulus $ℐ$, and the Reduce function can be used as a simplification function.

Gröbner bases are computable objects. The most popular method for computing them is Buchberger's algorithm ( [47] , [46] ). It has several variants and it is implemented in most of general computer algebra systems like Maple or Mathematica. The computation of Gröbner bases using Buchberger's original strategies has to face to two kind of problems :

• (A) arbitrary choices : the order in which are done the computations has a dramatic influence on the computation time;

• (B) useless computations : the original algorithm spends most of its time in computing 0.

For problem (A), J.C. Faugère proposed ([4] - algorithm $F_4$) a new generation of powerful algorithms ([4] ) based on the intensive use of linear algebra technics. In short, the arbitrary choices are left to computational strategies related to classical linear algebra problems (matrix inversions, linear systems, etc.).

For problem (B), J.C. Faugère proposed ([3] ) a new criterion for detecting useless computations. Under some regularity conditions on the system, it is now proved that the algorithm do never perform useless computations.

A new algorithm named $F_5$ was built using these two key results. Even if it still computes a Gröbner basis, the gap with existing other strategies is consequent. In particular, due to the range of examples that become computable, Gröbner basis can be considered as a reasonable computable object in large applications.

We pay a particular attention to Gröbner bases computed for elimination orderings since they provide a way of "simplifying" the system (equivalent system with a structured shape). A well known property is that the zeros of the first non null polynomial define the Zariski closure (classical closure in the case of complex coefficients) of the projection on the coordinate's space associated with the smallest variables.

Such kinds of systems are algorithmically easy to use, for computing numerical approximations of the solutions in the zero-dimensional case or for the study of the singularities of the associated variety (triangular minors in the Jacobian matrices).

Triangular sets have a simplier structure, but, except if they are linear, algebraic systems cannot, in general, be rewritten as a single triangular set, one speaks then of decomposition of the systems in several triangular sets.

Triangular sets appear under various names in the field of algebraic systems. J.F. Ritt ( [64] ) introduced them as characteristic sets for prime ideals in differential algebra. His constructive algebraic tools were adapted by W.T. Wu in the late seventies for geometric applications. The concept of regular chain (see [56] and [74] ) is adapted for recursive computations in a univariate way.

It provides a membership test and a zero-divisor test for the strongly unmixed dimensional ideal it defines. Kalkbrenner defined regular triangular sets and showed how to decompose algebraic varieties as a union of Zariski closures of zeros of regular triangular sets. Gallo showed that the principal component of a triangular decomposition can be computed in $O\left(d^{O\left(n^2\right)}\right)$ ($n$= number of variables, $d$=degree in the variables). During the 90s, implementations of various strategies of decompositions multiply, but they drain relatively heterogeneous specifications.

D. Lazard contributed to the homogenization of the work completed in this field by proposing a series of specifications and definitions gathering the whole of former work [1] . Two essential concepts for the use of these sets (regularity, separability) at the same time allow from now on to establish a simple link with the studied varieties and to specify the computed objects precisely.

A remarkable and fundamental property in the use we have of the triangular sets is that the ideals induced by regular and separable triangular sets, are radical and equidimensional. These properties are essential for some of our algorithms. For example, having radical and equidimensional ideals allows us to compute straightforwardly the singular locus of a variety by canceling minors of good dimension in the Jacobian matrix of the system. This is naturally a basic tool for some algorithms in real algebraic geometry [2] , [7] , [67] .

In 1993, Wang [70] proposed a method for decomposing any polynomial system into fine triangular systems which have additional properties such as the projection property that may be used for solving parametric systems (see Section  3.4.2 ).

Triangular sets based techniques are efficient for specific problems, but the implementations of direct decompositions into triangular sets do not currently reach the level of efficiency of Gröbner bases in terms of computable classes of examples. Anyway, our team benefits from the progress carried out in this last field since we currently perform decompositions into regular and separable triangular sets through lexicographical Gröbner bases computations.